package 面试题39_数组中出现超过一半的数字.实现一_找中位数快排思路;

import java.util.Random;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 10:40 2021/3/10
 * @Description：
 */
public class Solution {
    public int majorityElement(int[] nums) {
        if (nums.length <= 0) {
            return 0;
        }

        int middle = nums.length >> 1;// 中间位置索引

        int start = 0, end = nums.length - 1;

        int index = partition(nums, start, end);

        while (index != middle) {
            // 在左边
            if (index > middle) {
                end = index - 1;
                index = partition(nums, start, end);
            } else {
                start = index + 1;
                index = partition(nums, start, end);
            }
        }

        int result = nums[index];
        return result;

    }

    int partition(int[] data, int start, int end) {
        // 随机选取轴值
        Random random = new Random();
        int index = start + (int) (random.nextDouble() * (end - start + 1));
        int value = data[index];//轴值

        // 将选取的这个索引值放到子序列的第一个位置
        swap(data, start, index);

        // 设置两个指针，指向最左和最右
        int i = start, j = end;

        while (i < j) {
            // 从后向前扫描，比较和轴值的大小，若比轴值大，则继续扫描，否则将较小的值和轴值交换
            while (i < j && value <= data[j]) {
                j--;
            }
            if (i < j) {
                // 当前面的while条件不满足时表示右边的值比左边的小，则执行交换
                swap(data, i, j);
            }
            // 从前向后扫描，比较与轴值的小，若比轴值小，则不动，继续扫描
            while (i < j && value >= data[i]) {
                i++;
            }
            if (i < j) {
                swap(data, i, j);
            }
        }

        return i;
    }

    void swap(int[] data, int index1, int index2) {
        int temp = data[index1];
        data[index1] = data[index2];
        data[index2] = temp;
    }
}
